package demo.practice.leetcode;

import java.util.ArrayList;
import java.util.List;

public class P99 {

    public static void main(String[] args) {
        //[3,1,4,null,null,2]
        TreeNode root = new TreeNode(3);
        root.left= new TreeNode(1);
        root.right=new TreeNode(4);
        root.right.left=new TreeNode(2);

        P99 p99 = new P99();
        p99.recoverTree(root);
        System.out.println("xx");
    }

    //          3
    //       1      4
    //            2

    //https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/
    /**
     *
     */
    ArrayList<TreeNode> list = new ArrayList<>();
    public void recoverTree(TreeNode root) {
        foreach(root);//123456789  183456729
        int o1 = -1;
        int o2 = -1;

        //183456729  会得到  8>3  7>2  不满足  arr[i]<arr[i+1]
        //1324       会得到  3>2 不满足 arr[i]<arr[i+1]
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i).val > list.get(i + 1).val ) {
                //有点儿难理解
                if(o1==-1){//第一次赋值找到第一个 为o1，找到之后就不再改变了。
                    o1=i;
                }
                o2=i+1;//如果只有一个交换的值，o2就位i+1  但如果找到两个，则用后面的覆盖
            }
        }

        Integer tmp = list.get(o1).val;
        list.get(o1).val = list.get(o2).val;
        list.get(o2).val = tmp;



    }


    public int[] findTwoSwapped(List<Integer> nums) {
        int n = nums.size();
        int x = -1, y = -1;
        for (int i = 0; i < n - 1; ++i) {
            if (nums.get(i + 1) < nums.get(i)) {
                y = nums.get(i + 1);
                if (x == -1) {
                    x = nums.get(i);
                } else {
                    break;
                }
            }
        }
        return new int[]{x, y};
    }


    public void foreach(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            foreach(root.left);
        }
        list.add(root);
        if (root.right != null) {
            foreach(root.right);
        }
    }


}
